package com.cuz.daileetcode;

/****
 * 见
 * DaiLeetCode49打包机器物品移动问题
 */
public class Day49 {


    /****
     * 打包机器物品移动问题
     */
    static class PackingGoods {
        static int solution1(int[] goods) {
            if (goods == null || goods.length == 0) {
                return 0;
            }
            int len = goods.length;
            int sum = sumOf(goods);
            //无法整除说明无法平衡
            if (sum % len != 0) {
                return -1;
            }
            //每个地方达到平衡需要商品数目
            int avg = sum / len;
            //当前位置 左侧的商品输了
            int leftGoodSum = 0;
            //需要移动多少次
            int goodNeedMoveCount = 0;
            for (int index = 0; index < goods.length; index++) {
                //正数代表当前位置需要从一侧拿到多少物品
                //对于当前位置，需要向左侧 丢多少件（如果是负数 那么就是需要左侧给多少件）
                int leftGoodShouldMove = leftGoodSum - index * avg;
                //当前位置需要向右侧丢多少件 （如果是负数 那么就是需要右侧给多少件）
                int rightGoodShouldMove = sum - leftGoodSum - goods[index] - (len - index - 1) * avg;
                //如果当前位置非常缺少，需要左侧给，需要右侧给 那么当前位置为了达到合适的数目，
                // 需要左侧给了，再等右侧给了，也就是二者绝对值之和
                if (leftGoodShouldMove < 0 && rightGoodShouldMove < 0) {
                    goodNeedMoveCount = Math.max(goodNeedMoveCount, Math.abs(leftGoodShouldMove + rightGoodShouldMove));
                } else {
                    //如果左侧 右侧不全为负数
                    //均为正，那么需要到左侧给 和右侧给，但是两侧可以同时进行 所以是二者最大值
                    //一正一负，可以接受一侧的同时给予另外一侧，也是二者绝对值最大值
                    goodNeedMoveCount = Math.max(goodNeedMoveCount,
                            Math.max(leftGoodShouldMove, rightGoodShouldMove));
                }
                //更新前缀和
                leftGoodSum += goods[index];
            }
            //goodNeedMoveCount 拿到了所有位置达到平衡的的最大移动数目，就是整个达到平衡最大的数目
            return goodNeedMoveCount;
        }

        static int sumOf(int[] arr) {
            int sum = 0;
            for (int temp : arr) {
                sum += temp;
            }
            return sum;
        }

    }

    static class RotaryPrintMatrix {

        public static void main(String[] args) {
            int[][] arr = {
                    new int[]{0, 1, 2, 3},
                    new int[]{4, 5, 6, 7},
                    new int[]{8, 9, 10, 11},
            };
            rotaryPrintMatrix(arr);
        }

        static void rotaryPrintMatrix(int[][] matrix) {
            if (matrix == null) {
                return;
            }
            int rowEnd = matrix.length - 1;
            int colEnd = matrix[0].length - 1;
            int rowStart = 0;
            int colStart = 0;
            //如果没有错开
            while (rowStart <= rowEnd && colStart <= colEnd) {
                printEdge(matrix, rowStart++, colStart++, rowEnd--, colEnd--);
            }
        }

        private static void printEdge(int[][] matrix, int rowStart, int colStart, int rowEnd, int colEnd) {
            //同一行 那么从 colStart打印到colEnd
            if (rowStart == rowEnd) {
                while (colStart <= colEnd) {
                    System.out.print(matrix[rowStart][colStart] + " ");
                    colStart++;
                }
                return;
            }
            //同一列 那么从 rowStart 打印到rowEnd
            if (colStart == colEnd) {
                while (rowStart <= rowEnd) {
                    System.out.print(matrix[rowStart][colStart] + " ");
                    rowStart++;
                }
                return;
            }
            int curRow = 0;
            int curCol = 0;
            //左到右
            while (curCol < colEnd) {
                System.out.print(matrix[rowStart][curCol] + " ");
                curCol++;
            }
            //上到下
            while (curRow < rowEnd) {
                System.out.print(matrix[curRow][colEnd] + " ");
                curRow++;
            }
            //右到左
            while (curCol > colStart) {
                System.out.print(matrix[rowEnd][curCol] + " ");
                curCol--;
            }
            //右到左
            while (curRow > rowStart) {
                System.out.print(matrix[curRow][colStart] + " ");
                curRow--;
            }
        }
    }

    static class Rotary90 {
        public static void rotate(int[][] matrix) {
            int tR = 0;
            int tC = 0;
            int dR = matrix.length - 1;
            int dC = matrix[0].length - 1;
            while (tR < dR) {
                rotateEdge(matrix, tR++, tC++, dR--, dC--);
            }
        }

        public static void rotateEdge(int[][] m, int a, int b, int c, int d) {
            int tmp = 0;
            //i记录第几轮
            //第一轮的点是四个顶点
            //第二轮是 左上角顶点横坐标不变纵坐标+1.右上角顶点横坐标-1 纵坐标不变。。。
            for (int i = 0; i < d - b; i++) {
                tmp = m[a][b + i];
                m[a][b + i] = m[c - i][b];
                m[c - i][b] = m[c][d - i];
                m[c][d - i] = m[a + i][d];
                m[a + i][d] = tmp;
            }
        }
    }
}
